#pragma once
#ifndef __NFA__H__
#define __NFA__H__

#include <map>
#include <set>
#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <stdio.h>
#include <sstream>
#include <stack>
#include <queue>
#include <algorithm>
#include <unordered_map>
using namespace std;



//单词符号的类型，返回<待测代码中的单词符号,WordType>
typedef enum WordType
{ 
    //当识别成标识符后， 先判断是不是保留字，让后再判断IDN
    KW_INT = 1, // int
    KW_VOID = 4, // void
    KW_RETURN = 5, // return
    KW_CONST = 6, // const
    KW_CHAR, //char
    OP_EXC = 8, // !
    OP_ADD = 9, // +
    OP_SUB = 10, // -
    OP_MUL = 11, // *
    OP_DIV = 12, // /
    OP_MOD = 13, // %
    OP_ASSIGN = 14, // =
    OP_GT = 15, // >
    OP_LT = 16, // <
    OP_EQ = 17, // ==
    OP_LE = 18, // <=
    OP_GE = 19, // >=
    OP_NE = 20, // !=
    OP_AND = 21, // &&
    OP_OR = 22, // ||

    SE_LBRAC = 23, // ( left backet
    SE_RBRAC = 24, // ) right bracket
    SE_LCBRAC = 25, // { left curly bracket
    SE_RCBRAC = 26, // } right curly bracket
    SE_SEMI = 27, // ;
    SE_COMMA = 28, // ,
    SE_COLON = 29, // :
    SE_Single = 36, // '
    IDN, // [a-zA-Z][a-zA-Z_0-9]*
    INT_VAL, // -*[0-9]+

    CHAR_VAL, // '[a-zA-Z]'

    FLOAT_VAL, //
    CHAR_B,
    UNKOWN
} WordType;

string getWordTypeName(WordType type);
string getWordTypeContent(WordType type,string buffer);
//定义输入的字符类别
typedef enum InputCharType
{
    LETTER = 0, // 字母					0
    UNDERLINE, // _ 					1
    DIGIT, // 数字					2  当识别成功一个数字时，为了避免出现数字01的情况，返回前先进行一个判断，对GCC，01可以识别并等于1的
    //OP
    ADD, // +					3
    SUB, // -					4
    MUL, // *					5
    DIV, // /					6
    MOD, // %					7
    EQ, // =					8
    GT, // >					9
    LT, // <					10
    NOT, // !					11
    AND, // &					12
    OR, // |					13
    //SE
    LBRACKET, // (					14
    RBRACKET, // )					15
    LCBRAC, // {					16
    RCBRAC, // }					17
    COMMA, // ,					18
    SEMI, // ;					19
    SINGLE, // 单引号               20
    POINT, //. 小数
    MAO, // :
    BACKQUOTE,
    EPSILON, // 空字符				21
} InputCharType;

string getInputChartypeName(InputCharType type);

enum class TokenType
{
    KW = 0,
    OP,
    SE,
    IDN,
    INT,
    CHAR,
    FLOAT_VAL,
    UNKNOWN
};

TokenType getTokenType(WordType wordType, string buffer);

typedef struct Token
{
    string value;
    TokenType type;
} Token;

//定义函数判断输入的字符类别
InputCharType getInputCharType(char c);
string getWordTypeName(WordType type, string buffer);

//定义状态类
class State
{
public:
    int id; // 状态编号
    map<InputCharType, set<State*>> transitions; // 转移函数映射表，记录每个输入字符类型对应的目标状态集合
    bool isFinalState; // 是否为最终状态
    WordType wordType; // 到达该状态时应该返回的词法单元类型
    State(int id) : id(id), isFinalState(false), wordType(UNKOWN)
    {
    }

    void addTransition(InputCharType input, State* targetState)
    {
        transitions[input].insert(targetState);
    }

    void setFinalState(bool isFinal, WordType type)
    {
        isFinalState = isFinal;
        wordType = type;
    }

    bool operator<(const State& other) const
    {
        return id < other.id;
    }
};

//为了是set内部有序，定义排序结构体StatePtrCompare
struct StatePtrCompare
{
    bool operator()(const State* lhs, const State* rhs) const
    {
        return lhs->id < rhs->id;
    }
};

//定义NFA类
class RegextoNFA
{
public:
    State* startState; // 起始状态
    set<State*, StatePtrCompare> endStates; // 终止状态集合
    set<State*, StatePtrCompare> states; // 状态集合
    RegextoNFA(State* startState, set<State*, StatePtrCompare> endStates, set<State*, StatePtrCompare> states) :
        startState(startState), endStates(endStates), states(states)
    {
    }

    // void printNFA();
};

RegextoNFA regexToNFA();
void printNFA(const RegextoNFA& nfa);
RegextoNFA buildNFA(string filename);
RegextoNFA regexToNFA();
set<State*, StatePtrCompare> move(const set<State*, StatePtrCompare>& states, InputCharType input);
set<State*, StatePtrCompare> epsilonClosure(const set<State*, StatePtrCompare>& states);

class miniDFA
{
public:
    State* startState; // 起始状态
    set<State*, StatePtrCompare> endStates; // 终止状态集合
    set<State*, StatePtrCompare> states; // 状态集合
    miniDFA(State* startState, set<State*, StatePtrCompare> endStates, set<State*, StatePtrCompare> states) :
        startState(startState), endStates(endStates), states(states)
    {
    }
};

void removeUnreachableStates(miniDFA& dfa);
void printDFA(const miniDFA& dfa);
miniDFA nfaToDFA(const RegextoNFA& nfa);
void printDFA(const miniDFA& dfa);

struct SetComparator
{
    bool operator()(const set<State*, StatePtrCompare>& a, const set<State*, StatePtrCompare>& b) const
    {
        if (a.size() != b.size())
        {
            return a.size() < b.size();
        }

        vector<State*> vecA(a.begin(), a.end());
        vector<State*> vecB(b.begin(), b.end());

        sort(vecA.begin(), vecA.end(), [](const State* a, const State* b) { return a->id < b->id; });
        sort(vecB.begin(), vecB.end(), [](const State* a, const State* b) { return a->id < b->id; });

        return vecA < vecB;
    }
};

miniDFA minimizeDFA(const miniDFA& dfa);
void analyze(const miniDFA& dfa, const string& input, const string& output);
string readfile(string filename);
#endif
